package tree

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

/*
https://leetcode-cn.com/problems/convert-bst-to-greater-tree/solution/ba-er-cha-sou-suo-shu-zhuan-huan-wei-lei-jia-sh-14/
空间复杂度:O(N) 每个节点访问一次
时间复杂度:O(N) 栈空间(最坏情况程链状)

Mirros算法????
 */
// 对二叉搜索树计算大于等于每一个节点的数字和
// 可以转化为逆中序遍历，在遍历到当前节点时，将之前的所有节点的数字和相加，然后复制到当前节点
func convertBST(root *TreeNode) *TreeNode {
	sum := 0
	var dfs func(*TreeNode)
	dfs = func(node *TreeNode) {
		if node != nil {
			dfs(node.Right)
			// 将逆中序遍历过程中，所有在自己之前遍历到的节点的数字相加，保存到sum
			sum += node.Val
			node.Val = sum
			dfs(node.Left)
		}
	}
	dfs(root)
	return root
}
